import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TestDem012A {
}
//最小栈
class MinStack{
    Stack<Integer>stack;
    Stack<Integer>minStack;
    public MinStack(){//构造两个栈，一个普通栈，一个辅助栈
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    public void push(int val){
        stack.push(val);
        if(minStack.isEmpty()){//如果辅助栈第一次存放元素，直接入栈
            minStack.push(val);
        }else{
            if(minStack.peek()>val){//如果普通栈入栈的元素小于辅助栈顶元素，直接入栈
                minStack.push(val);
            }
        }
    }
    public void pop(){
        //这里要用eqauls，不能用==，pop方法和peek方法方法返回的是objec
        if(stack.pop().equals(minStack.peek())){
            minStack.pop();
        }
    }
    public int top(){
        if(stack.isEmpty()){
            return -1;
        }
        return  stack.peek();
        }
        public int getMin(){
        if(minStack.isEmpty()){
            return -1;
        }
        return minStack.peek();
    }

    //括号匹配问题
    public boolean isValid(String s){
        if(s==null||s.length()==0){
            return true;
        }
        Stack<Character>stack=new Stack<>();//栈的目的是为了加入左括号
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){//栈为空，左括号没有了，右括号多的情况
                    return false;
                }
                char tem=stack.peek();
                //左括号与右括号是否匹配，匹配就出栈
                if(ch==')'&&tem=='('||ch==']'&&tem=='['||ch=='}'&&tem=='{'){
                    stack.pop();//
                }
                else{//一旦不匹配就直接false
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){//打印完之后，看栈里面是否为空，如果有说明左括号多，右括号少，不满足。
            return false;
        }else{
            return true;
        }
    }
}

//用队列实现栈
class myStack {
    Queue<Integer> qu1;
    Queue<Integer> qu2;

    public myStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    public void push(int val) {
        if (empty()) {
            qu1.offer(val);
        } else {
            if (qu1.isEmpty()) {
                qu2.offer(val);
            }
            if (qu2.isEmpty()) {
                qu1.offer(val);
            }
        }
    }

    public int pop() {
        if (empty()) {
            return -1;
        } else {
            if (qu1.isEmpty()) {
                int size = qu2.size() - 1;
                while (size > 0) {
                    int val = qu2.poll();
                    qu1.offer(val);
                    size--;
                }
                return qu2.poll();
            } else {
                int size = qu1.size() - 1;
                while (size > 0) {
                    int val = qu1.poll();
                    qu2.offer(val);
                    size--;
                }
            }
            return qu1.poll();
        }
    }

    public int top() {
        if (empty()) {
            return -1;
        }
        if (qu1.isEmpty()) {
            int size = qu2.size();
            int val = 0;
            while (size > 0) {
                val = qu2.poll();
                qu1.offer(val);
                size--;
            }
            return val;
        } else {
            int size = qu1.size();
            int val = 0;
            while (size > 0) {
                val = qu1.poll();
                qu2.offer(val);
                size--;
            }
            return val;

        }
    }
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}
//用栈实现队列
 class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        int tem = 0;
        while (!stack1.isEmpty()) {
            tem = stack1.pop();
            stack2.push(tem);
        }
        return stack2.pop();
    }

    public int peek() {
        int tem = 0;
        while (!stack1.isEmpty()) {
            tem = stack1.pop();
            stack2.push(tem);
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}
    //实现循环队列
    class MyCircularQueue {
        private int[] elem;
        private int front;
        private int rear;

        public MyCircularQueue(int k) {
            elem = new int[k + 1];
            front = 0;
            rear = 0;

        }

        public boolean enQueue(int value) {
            if (isFull()) {
                return false;
            } else {
                elem[rear] = value;
                rear = (rear + 1) % elem.length;
                return true;
            }
        }

        public boolean deQueue() {
            if (isEmpty()) {
                return false;
            } else {
                front = (front + 1) % elem.length;
                return true;
            }
        }
        public int Front(){
            if(isEmpty()){
                return -1;
            }
            return elem[front];
        }
        public int Rear() {
            if (isEmpty()) {
                return -1;
            } else {
                int index = (rear == 0) ? elem.length - 1 : rear - 1;
                return elem[index];
            }
        }
            public boolean isEmpty(){
                if(front==rear){
                    return true;
                }
                else{
                    return false;
                }
            }

            public boolean isFull(){
            if((rear+1)%elem.length==front){
                return true;
            }
            return false;
            }
    }


